import networkx as nx
import DC_CLASS as dc
import USER_CLASS as uc
import VERTEX_CLASS as vc
import random
import copy as cp
import itertools as it

class MyGraph(nx.Graph):
    NULL = 1000000
    USERS_PER_VM = 5
    PATHS_PER_SERVER = 50
    LOW_DC_DIST_BOUND = .25
    HIGH_DC_DIST_BOUND = .75
    LOW_USER_DIST_BOUND = 1
    HIGH_USER_DIST_BOUND = 1.5
    def __init__(self, Group_List, Num_DCs, Max_Lat = 700):
        nx.Graph.__init__(self)
        self.DC_List = []
        self.User_List = []
        self.NUM_DCS = Num_DCs
        self.MAX_LATENCY = Max_Lat
        self.NUM_GROUPS = len(Group_List)
        self.Group_Sizes = Group_List
        i = 0;
        while i < Num_DCs: 
            a = dc.DC()
            self.DC_List.append(a)
            i = i + 1

        i = 0
        self.NUM_USERS = 0
        while i < len(Group_List):
            j = 0
            while j < Group_List[i]:
                a = uc.User(i)
                self.User_List.append(a)
                self.NUM_USERS = self.NUM_USERS + 1
                j = j + 1

            i = i + 1
            
            
        self.add_nodes_from(self.DC_List)
        self.add_nodes_from(self.User_List)
    
        for n1 in self.nodes():
            for n2 in self.nodes():
                if n1 is not n2:
                    if type(n1) is uc.User and type(n2) is dc.DC:
                        self.add_edge(n1, n2)
                    if type(n1) is dc.DC and type(n2) is dc.DC:
                        self.add_edge(n1, n2)
                        
    ##############################################################################
    def Set_Latencies(self):
        for (n1, n2) in self.edges():
            if type(n1) is dc.DC and type(n2) is dc.DC:
                self[n1][n2]['latency'] = vc.dist(n1, n2) * \
                    random.uniform(self.LOW_DC_DIST_BOUND, self.HIGH_DC_DIST_BOUND)
            else:
                self[n1][n2]['latency'] = vc.dist(n1, n2) * \
                    random.uniform(self.LOW_USER_DIST_BOUND, self.HIGH_USER_DIST_BOUND)
        
    #############################################################################
    # So the DC owners can be any of 'a', 'b', 'c', distruibuted equally
    def Set_DC_Owners(self):
        i = 0
        owner_list = ['a', 'b', 'c']
        for n1 in self.DC_List:
            self.node[n1]['owner'] = owner_list[i % 3]
            i = i + 1
        
    ############################################################################
    # costs are measured in dollars/GB
    def Set_Edge_Costs(self):
        for n1 in self.DC_List:
            for n2 in self.DC_List:
                if n1 is not n2:
                    if self.node[n1]['owner'] is self.node[n2]['owner']:
                        self[n1][n2]['cost'] = .03
                    else:
                        self[n1][n2]['cost'] = .12
                
        for Dc in self.DC_List:
            for Us in self.User_List:
                self[Dc][Us]['cost'] = .12
        
    ############################################################################
    def Set_DC_Costs(self):
        for n1 in self.DC_List:
            self.node[n1]['cost'] = .06
            
    ###########################################################################
    def Set_Max_Lats(self):
        MaxLat = 0
        for Dc in self.DC_List:
            MaxLat = 0
            for Us in self.User_List:
                if self[Dc][Us]['latency'] > MaxLat:
                    MaxLat = self[Dc][Us]['latency']
            Dc.MaxLat = MaxLat
        
    ############################################################################
    def Find_Optimal_Path_Set(self):
        #this holds a list of tuples that the function returns.
        Return_List = []
        for Dc in self.DC_List:
            Current_DC = Dc
            self.DC_List.remove(Dc)
            Bucket_List = []
            for Us in self.User_List:
                Bucket_List.append([])
                for Subset_Size in range(self.NUM_DCS):
                    for Combo in it.combinations(self.DC_List, Subset_Size):
                        for Perm in it.permutations(Combo):
                            #print(Perm)
                            if self.Calc_Latency_Of_DC_List(list(Perm), Us, Dc) < self.MAX_LATENCY:
                                Bucket_List[self.User_List.index(Us)].append(list(Perm))   
            self.DC_List.insert(0, Current_DC)
            Temp_List = list(self.Least_Cost_Path_Set(Bucket_List, Current_DC))
            Temp_List.insert(0, Current_DC)
            Return_List.append(Temp_List)
            
        #this calculates which element of Return_List is our optimal solution
        Low_Cost = self.NULL
        Host = None
        Best_Path = []
        for Opt_Host_Set in Return_List:
            if Opt_Host_Set[2] < Low_Cost:
                Best_Path = Opt_Host_Set
                Low_Cost = Opt_Host_Set[2]
                
        if Low_Cost == self.NULL:
            Best_Path.append(None)
            Best_Path.append(None)
            Best_Path.append(self.NULL)
        
        return Best_Path
            
        
        
    ###########################################################################
    # this guy orders the DC_List (least --> greatest)
    def Order_DC_List(self):
        self.DC_List.sort(key = dc.DC.Return_MaxLat)

    ##########################################################################        
    def Calc_Latency_Of_DC_List(self, list_of_DCs, User, Data_Center):
        latency = 0
        if len(list_of_DCs) is 0:
            #print("stuckhere")
            return self[Data_Center][User]['latency']
        if Data_Center in list_of_DCs:
            return self.NULL
        latency = latency + self[Data_Center][list_of_DCs[0]]['latency']
        list_of_DCs.append(User)
        i = 0
        while i < len(list_of_DCs) - 1:
            latency = latency + self[list_of_DCs[i]][list_of_DCs[i + 1]]['latency']
            i = i + 1
        list_of_DCs.pop()
        return(latency)
    
    ###########################################################################
    #this guy calculates the edge costs for a specified user, DC, and
    #list of forwarding DCs, DC COSTS NOT INCLUDED
    def Calc_Cost_Of_DC_List(self, list_of_DCs, User, Data_Center):
        cost = 0
        if len(list_of_DCs) is 0:
            #print("stuckhere")
            return self[Data_Center][User]['cost']
        if Data_Center in list_of_DCs:
            return self.NULL
        cost = cost + self[Data_Center][list_of_DCs[0]]['cost']
        list_of_DCs.append(User)
        i = 0
        while i < len(list_of_DCs) - 1:
            cost = cost + self[list_of_DCs[i]][list_of_DCs[i + 1]]['cost']
            i = i + 1
        list_of_DCs.pop()
        return(cost)
    
    ##########################################################################
    #This returns the DC's cost, so that it can be used in the above sorting algorithm
    #, so that we can use combinations of costs as keys
    def Get_DC_List_Cost(self, Data_Center_List):
        cost = 0
        for DC in Data_Center_List:
            cost = cost + self.node[DC]['cost']
        return(cost)
    
    #########################################################################
    #Checks if the SmallList is a sublist of hte BigList
    def Check_Sublist(self, SmallList, BigList):
        for element in SmallList:
            if element not in BigList:
                return False
        return True
    
    ##########################################################################        
    # takes in a list of list of lists (for each user, a list of all possible
    # paths to that user (represented as lists of data centers). returns the least
    # cost set of paths from the given data center to each user. 
    # paths is a list of list of list. 
    def Least_Cost_Path_Set(self, paths, Current_DC):
        best_path_set = None
        best_path_set_cost = 9999999
        all_path_sets = self.all_paths(paths)
        for x in all_path_sets:
            cost = self.calc_edge_cost(x, Current_DC) + self.calc_server_cost(x)
            if cost < best_path_set_cost:
                best_path_set_cost = cost
                best_path_set = x
        return (best_path_set, best_path_set_cost)
    
    # takes in a list of paths by user and returns a list of all path combos
    def all_paths(self, list_of_paths_by_user):
        all_combos = []
        combo = []
        self.all_paths_helper(list_of_paths_by_user, combo, all_combos)
        return all_combos
    
    # helper for all_paths
    def all_paths_helper(self, list_of_paths_by_user, combo, all_combos):
        if list_of_paths_by_user:
            for x in list_of_paths_by_user[0]:
                already_examined = list_of_paths_by_user.pop(0)
                combo.append(x)
                self.all_paths_helper(list_of_paths_by_user, combo, all_combos)
                list_of_paths_by_user.insert(0, already_examined)
                combo.pop()
        else:
            all_combos.append(cp.copy(combo))
    
    # calculate edge costs for a given path set
    def calc_edge_cost(self, path_set, Current_DC):
        edge_cost_dict = {}
        for x in range(len(path_set)):
            path = path_set[x]
            if len(path) > 0:
                DC1 = Current_DC
                DC2 = path[0]
                cost = self[DC1][DC2]['cost']
                edge_cost_dict[(DC1, DC2)] = cost
                for y in range(len(path) - 1):
                    DC1 = path[y]
                    DC2 = path[y+1]
                    cost = self[DC1][DC2]['cost']
                    edge_cost_dict[(DC1, DC2)] = cost
                
        sum = 0
        for x in edge_cost_dict.values():
            sum = sum + x
        # for the cost of edges to users
        sum = sum + .12*self.NUM_USERS
        return sum
        
    # calculate server cost for a given path set
    def calc_server_cost(self, path_set):
        server_cost_dict = {}
        for x in range(len(path_set)):
            path = path_set[x]
            for y in range(len(path)):
                DC = path[y]
                cost = self.node[DC]['cost']
                server_cost_dict[DC] = cost
        sum = 0
        for x in server_cost_dict.values():
            sum = sum + x
        return sum
        